package linkedlist;

/**
 * Created by Tzachi on 14/10/2014.
 */
public class NthToLastElement {
    static Node nthToLastIterative(Node<Integer> head, int n) {
        if (head == null || n < 1) {
            return null;
        }
        Node<Integer> p1 = head;
        Node<Integer> p2 = head;
        for (int j = 0; j < n - 1; j++) { // skip n-1 steps ahead
            if (p2 == null) {
                return null; // not found since list size < n
            }
            p2 = p2.getNext();
        }
        while (p2.getNext() != null) {
            p1 = p1.getNext();
            p2 = p2.getNext();
        }
        return p1;
    }

    static int i = 0;
    static void nthToLastRecursion(Node<Integer> head, Node<Integer> nth, int n) {
        if (head == null) {
            return;
        }
        nthToLastRecursion(head.getNext(), nth, n);
        i++;
        if (i == n) {
            nth.setNext(head.getNext());
            nth.setData(head.getData());
        }
    }

}
